package com.hdu.other.binarySearch;



public class lc2141 {
    class Solution {
        public long maxRunTime(int n, int[] batteries) {
            long l = 0, r = 0, ans = 0;
            for (int i = 0; i < batteries.length; i++) {
                r += batteries[i];
            }
            while (l <= r) {
                long singleRunTime = (l + r) / 2;
                if (allCanRun(batteries, singleRunTime, n)) {
                    ans = singleRunTime;
                    l = singleRunTime + 1;
                } else {
                    r = singleRunTime - 1;
                }
            }
            return ans;
        }


        boolean allCanRun(int[] batteries, long singleRunTime, int n) {
            long sum = 0;
            for (int battery : batteries) {
                if (battery >= singleRunTime) n--;
                else sum += battery;
            }
            return n <= 0 || sum >= singleRunTime * n;
        }
    }
}
